// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* values -> Ponteiro para matriz de elementos    */
/* n      -> Numero de elementos computados       */
/* l      -> Posicao inicial do processo          */
void insertionSort(int values[], int n, int l = 0) {
  int r = n+l;
  int i, j;
  int t;
  int min;

  /* Coloca o menor elemento na primeira posicao (otimizacao do algoritmo) */
  /* Evita ficar verificando j negativo no algoritmo                       */
  min = l;
  for (i = l+1;i < r;++i)
    if (values[i] < values[min]) min = i;
  t = values[l]; values[l] = values[min]; values[min] = t;

  /* Ordena elementos restantes         */
  for (i = l+2;i < r;++i) {
    j = i;
    t = values[i];
    /* Coloca os maiores uma posicao a frente */
    while (t < values[j-1]) {
      values[j] = values[j-1];
      j--;
    }
    values[j] = t;
  }

  return;
}
